#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string.h>

// 打印数组的函数
void print_arr(int arr[], int left, int right) {
	for (int i = left; i <= right; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
}

// 归并排序的核心逻辑：merge
static void merge(int arr[], int left, int right, int mid, int *tmp) {
	// 初始化三个索引
	int tmp_left = left; // 合并中左子数组的开始索引
	int tmp_right = mid + 1; // 合并中右子数组的开始索引
	int tmp_idx = left;		// 合并结果的临时数组的开始索引

	while (tmp_left <= mid && tmp_right <= right) {	// 只要两个数组中都还有未处理的元素就继续循环处理
		if (arr[tmp_left] <= arr[tmp_right]) {	// 这个=必须要加，否则算法将不稳定。加了就是稳定排序算法
			// 把左半子区间的元素放入临时数组
			tmp[tmp_idx++] = arr[tmp_left++];
		}
		else {
			// 把右半子区间的元素放入临时数组
			tmp[tmp_idx++] = arr[tmp_right++];
		}
	}

	/*
		while结束后是什么情况？
		必然有一个数组是空的，而且也只有一个数组是空的
		另一个数组必然是还有元素的
		但是不知道哪一个数组还有元素，于是就判断
	*/
	while (tmp_left <= mid) {
		// 左半区间还有元素
		tmp[tmp_idx++] = arr[tmp_left++];
	}
	while (tmp_right <= right) {
		// 右半区间还有元素
		tmp[tmp_idx++] = arr[tmp_right++];
	}
	// 以上都结束了，意味着合并结束了。现在合并的结果在临时数组中，要把合并的结果复制回原始数组
	for (int i = left; i <= right; i++) {
		arr[i] = tmp[i];	// 原始数组和临时数组共用同一套下标
	}

	print_arr(arr, left, right);
}


static void divide_merge(int arr[], int left, int right, int *tmp) {
	// 递归的出口
	if (left >= right) {
		return;
	}
	// 递归体
	int mid = left + (right - left >> 1);
	divide_merge(arr, left, mid, tmp);
	divide_merge(arr, mid + 1, right, tmp);
	// 归并排序的核心逻辑合并
	merge(arr, left, right, mid, tmp);
}


void merge_sort(int arr[], int len) {
	// 在这里分配临时数组空间
	int *tmp = calloc(len, sizeof(int));
	if (tmp == NULL) {
		printf("error: calloc failed in merge_sort.\n");
		exit(-1);
	}
	divide_merge(arr, 0, len - 1, tmp);
	// 在这里free临时数组
	free(tmp);
}

int main(void) {
	int arr[] = { 8, 3, 2, 6, 9, 7, 1, 0, 4, 5 };
	int arr_size = sizeof(arr) / sizeof(arr[0]);

	merge_sort(arr, arr_size);
	return 0;
}